/**
 * Letter Combinations of a Phone Number
Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.



Input:Digit string "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.
 */
package com.xinpan.exercise;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LetterCombinationofPhoneNumber {
    public ArrayList<String> letterCombinations(String digits) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList<String> res = new ArrayList<String>();
        if(digits.length() == 0)
        {
            res.add("");
            return res;
        }
            
        int p = 0;
        Map<Integer, List<Character>> digitCMap = new HashMap<Integer, List<Character>>();
        for(int i = 2; i < 7; i++)
        {
            List<Character> cList = new ArrayList<Character>();
            for(int j = 0; j < 3; j++)
            {
                cList.add((char)('a'+p++));
            }
            digitCMap.put(i, cList);
        }
        for(int i = 7; i < 8; i++)
        {
            List<Character> cList = new ArrayList<Character>();
            for(int j = 0; j < 4; j++)
            {
                cList.add((char)('a'+p++));
            }
            digitCMap.put(i, cList);
        }
        for(int i = 8; i < 9; i++)
        {
            List<Character> cList = new ArrayList<Character>();
            for(int j = 0; j < 3; j++)
            {
                cList.add((char)('a'+p++));
            }
            digitCMap.put(i, cList);
        }
        for(int i = 9; i < 10; i++)
        {
            List<Character> cList = new ArrayList<Character>();
            for(int j = 0; j < 4; j++)
            {
                cList.add((char)('a'+p++));
            }
            digitCMap.put(i, cList);
        }
        
        
        int val = Integer.valueOf(digits.charAt(0)-'0');
        List<Character> cList = digitCMap.get(val);
        for(int i = 0; i < cList.size(); i++)
            res.add(cList.get(i).toString());
            
        for(int i = 1; i < digits.length(); i++)
        {
            cList = digitCMap.get(Integer.valueOf(digits.charAt(i) - '0'));
            int len = res.size();
            for(int j = 0; j < len; j++)
            {
                String tmpStr = res.remove(0);
                for(int k = 0; k < cList.size(); k++)
                {
                    String newStr = new String(tmpStr + cList.get(k));
                    res.add(newStr);
                }
            }
        }
        
        return res;
    }
    
    
    public static void main(String[] args)
    {
    	LetterCombinationofPhoneNumber lcpn = new LetterCombinationofPhoneNumber();
    	lcpn.letterCombinations("2");
    }
}
